package m202405.d18;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/18 14:49
 */
public class Q42 {

    public static void main(String[] args) {
        Q42 q42 = new Q42();
        q42.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }

    public int trap(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        rightMax[rightMax.length - 2] = height[rightMax.length - 1];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
        }

        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            sum = sum + Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return sum;
    }
}
